﻿// 3445. 点菜问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;
/*
https://www.acwing.com/problem/content/3448/

北大网络实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为 C 元，
有 N 种菜可以点，经过长时间的点菜，网络实验室对于每种菜 i 都有一个量化的评价分数（表示这个菜可口程度），为 Vi
，每种菜的价格为 Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。

注意：由于需要营养多样化，每种菜只能点一次。

输入格式
输入的第一行有两个整数 C和 N，C 代表总共能够报销的额度， N代表能点菜的数目。

接下来的 N 行每行包括两个整数 Pi和 Vi
，分别表示第 i 道菜的价格和评价分数。

输出格式
输出共一行，一个整数，表示在报销额度范围内，所点的菜能够得到的最大评价分数。

数据范围
1≤C≤1000
,
1≤N≤100
,
1≤Pi,Vi≤100
输入样例：
90 4
20 25
30 20
40 50
10 18
输出样例：
95
*/


const int N = 200,M=1010;
int dp[N][M];
int p[N];
int v[N];

int n, c;

int main()
{
	cin >> c >> n;

	for (int i = 1; i <= n; i++) {
		cin >> p[i] >> v[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= c; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j >= p[i]) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - p[i]] + v[i]);
			}
		}
	}

	cout << dp[n][c] << endl;

	return 0;
}

 